public class Main {
    public static void main(String[] args) {

    }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    /**
     * 最小覆盖子串
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        int ns=s.length();
        int nt=t.length();
        char[] ss=s.toCharArray();
        char[] tt=t.toCharArray();
        int[] hash1=new int[128];
        int[] hash2=new int[128];
        int kinds=0,len=Integer.MAX_VALUE;
        int begin=-1;
        for(char str:tt){
            if(hash1[str]==0){
                kinds++;
            }
            hash1[str]++;
        }
        for(int left=0,right=0,count=0;right<ns;right++){
            char in=ss[right];
            if(++hash2[in]==hash1[in]){
                count++;
            }
            while(count==kinds){
                if(len>right-left+1){
                    len=right-left+1;
                    begin=left;
                }
                char out=ss[left];
                left++;
                if(hash2[out]--==hash1[out]){
                    count--;
                }
            }
        }
        if(begin==-1){
            return "";
        }else{
            return s.substring(begin,begin+len);
        }
    }
}